Deleting an Item at Position i - Educational Content

Deleting an Item in a Singly Linked List

Just as insertion required $O(n)$ traversal time, deletion carries the same time complexity burden because we must first find the predecessor node at position $i-1$.
Deleting a node simplifies the operation compared to insertion, requiring only **one** strategic pointer relinking step to bypass the target node.
The overall time complexity is determined by finding the correct insertion point: $O(n)$ (We traverse up to $i-1$ nodes).
The space complexity remains $O(1)$ as we only use fixed memory for pointers like $p$.
The deletion mechanism involves traversing the list using pointer $p$ until $p$ is at position $i-1$ (the predecessor).
The final step is the relink: update $p$'s `next` pointer to skip the node at position $i$ and point directly to its successor via: p.next = p.next.next.

Key Deletion Mechanism

By setting p.next = p.next.next, we effectively sever the link to the target node (at index $i$), making it unreachable from the list's head. This node is then eligible for garbage collection, completing the deletion.

Operation	Complexity	Pointers Used
Find Predecessor ($i-1$)	$O(n)$	$p$
Relink/Bypass	$O(1)$	$p$
Total Deletion Time	$O(n)$	$O(1)$

Linked List Deletion at Position i (Python)

1class Node:
2    # Reusing Node_Structure: {value, next}
3    def __init__(self, value, next_node=None):
4        self.value = value
5        self.next = next_node
6
7def delete_at_position(head, i):
8    # Handle deletion at head (i=0)
9    if i == 0:
10        if head is None:
11            return None
12        return head.next
13
14    p = head 
15    count = 0
16    # Traverse until p is at position i-1 (the predecessor)
17    while p is not None and count < i - 1: 
18        p = p.next
19        count += 1
20        
21    # Check for invalid index (p is NULL or deletion target is NULL)
22    if p is None or p.next is None:
23        print("Error: Index out of bounds.")
24        return head 
25        
26    # Perform the relinking/bypass: p skips p.next and points to p.next.next
27    # This deletes the node at index i
28    p.next = p.next.next 
29    
30    return head
31
32# Setup list: 10 -> 20 -> 30 -> 40
33head_ex = Node(10, Node(20, Node(30, Node(40))))
34
35# Delete 30 at index 2 (i=2, p stops at 20)
36head_ex = delete_at_position(head_ex, 2)
37
38# Verification output
39current = head_ex
40output = []
41while current:
42    output.append(str(current.value))
43    current = current.next
44print(" -> ".join(output))

Verification Output

After executing the deletion function for index $i=2$ (value 30), the resulting list structure is:

10 -> 20 -> 40